package com.mlh.dp.old;

// 题目：
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 举例：
// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
// 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

import java.util.Arrays;

public class LengthOfLIS {

    public static void main(String[] args) {
        int[] nums= {3,5,6,2,5,4,19,5,6,7,12};
        method2(nums);
        // int[] nums= {1,3,4,7,8,33,52,66,87,222};
        // System.out.println(find(nums,5));
    }


    //直白的解法   往前找到比当前nums[i]小的值   然后找到里面对应dp[x]最大的    dp[i]=dp[x]+1;
    //时间复杂度 n的2次方
    public static int method1(int[] nums) {
        int[] dp = new int[nums.length];//dp[i]含义是以nums[i]结尾的最长递增子序列
        boolean flag = false;
        int maxLen = 1;//记录最大长度
        //初始化
        dp[0]=1;

        for (int i = 1; i < nums.length; i++) {
            int max=0;//在i前面并且小于nums[i]的dp[]最大值
            int maxIndex=-1;//是上面那个dp[]的下标
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if(max<dp[j]){
                        maxIndex=j;
                        max=dp[j];
                    }
                    flag = true;
                }
            }
            if (flag) {
                dp[i]=dp[maxIndex]+1;
                maxLen = dp[i] > maxLen ? dp[i] : maxLen;
            }else {
                dp[i] = 1;
                maxLen = dp[i] > maxLen ? dp[i] : maxLen;
            }
            flag = false;
        }
        return maxLen;
    }


    //方法二：二分查找  自己写的
    public static int method2(int[]nums){
        int[]d=new int[nums.length];
        d[0]=nums[0];
        int len=0;
        int index=-1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>d[len]){
                d[++len]=nums[i];
            }else{
                index=find(nums[i],d,len);
                d[index+1]=nums[i];
            }
        }
        return len+1;
    }
    public static int find(int findNum,int[]d,int len){
        int l=0,r=len;
        int index=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(d[mid]<findNum){
                index=mid;  //这边的小于  且在这边记录 index  会影响最好找到的结果  这边index就会找到最后一个小于findNum的数的下标
                l=mid+1;    //对这步的理解至关重要   理解之后  想想能不能知道为什么不能用大于  来记录index  原因在ongestObstacleCourseAtEachPosition里面写了
            }else{
                r=mid-1;
            }
        }
        return index;
    }

    //leetcode官方代码
    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }


}
